package OJ;

import java.util.Scanner;

class ListNode{
    public int value;//当前节点的值
    public ListNode next;//当前节点的下一个节点

    public ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}
public class Main {

    public static ListNode createSingleList() {//创建单链表
        Scanner in = new Scanner(System.in);
        ListNode tail = null;
        ListNode head = null;

        int num = in.nextInt();//输入单链表的数据个数
        for (int i = 0; i < num; i++) {
            int value = in.nextInt();
            ListNode node = new ListNode(value);

            if(head == null) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                tail = node;
            }
        }

        in.close();
        return head;
    }

    public static ListNode reverseList(ListNode head) {//反转链表
        if(head == null) return null;//将头节点作为尾节点，然后使用尾插法从头节点前面插入
        ListNode prev= null;
        ListNode cur = head;

        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = prev;
            prev = cur;
            cur= curNext;
        }

        return prev;
    }

    public static void main(String[] args) {
        ListNode head = createSingleList();
        /*while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();*/
        head = reverseList(head);
        ListNode cur = head;
        while(cur != null) {
            System.out.print(cur.value + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public ListNode deleteAll (int val, ListNode head) {//删除所有值为value的元素
        if(head == null) return null;
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null) {
            if(cur.value == val) {//找到相同的
                //删除
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.value == val) {
            head = head.next;
        }
        return head;
    }

    //获取链表倒数第k个节点
    public ListNode getKth(int k, ListNode head) {
        //先反转链表
        reverseList(head);
        //然后返回顺数第k个节点
        ListNode cur = head;
        for (int i = 0; i < k; i++) {
            cur = cur.next;
        }
        return cur;
    }

}
